package com.lw.leetcode.arr.c;

/**
 * 668. 乘法表中第k小的数
 *
 * @Author liw
 * @Date 2021/5/12 16:36
 * @Version 1.0
 */
public class FindKthNumber {

    public static void main(String[] args) {
        FindKthNumber test = new FindKthNumber();
        int kthNumber = test.findKthNumber(42, 34, 401);
        System.out.println(kthNumber);

        int count = test.count(127, 42, 34);
        System.out.println(count);
    }

    public int findKthNumber(int m, int n, int k) {
        int st = 1;
        int end = m * n;
        while (st < end) {
            int r = st + ((end - st) >> 1);
            int count = count(r, m, n);
            if (count < k) {
                st = r + 1;
            } else {
                end = r;
            }
        }
        return end;
    }

    private int count(int mid, int m, int n) {
        int res = 0;
        for (int i = 1; i <= m; i++) {
            res += Math.min(mid / i, n);
        }
        return res;
    }
}
